#include "Bellman_Ford.hpp"


/**
 * @brief 单源最短路径算法初始化
 * 
 * @param G 输入的带权有向图
 * @param s 输入的源的索引
 */
void Bellman_Ford::Initialize_Single_Source(Weight_Directed_Graph *G, int s){
    for (size_t i = 0; i < (*G).n_V; i++)
    {
        (*G).V[i]->d = 2000000000;
        (*G).V[i]->pi = nullptr;
    }
    (*G).V[s]->d = 0;
}


/**
 * @brief Bellman-Ford算法中的松弛操作
 * 
 * @param u 第一个节点
 * @param v 第二个节点
 * @param w 邻接矩阵指针
 */
void Bellman_Ford::Relax(vertex* u, vertex* v, vector<vector<int>>* w){
    if(v->d > u->d + (*w)[u->index][v->index]){
        v->d = u->d + (*w)[u->index][v->index];
        v->pi = u;
    }
}


/**
 * @brief 运行Bellman-Ford算法
 * 
 * @param G 输入的图指针（用邻接表表示）
 * @param s 源节点索引
 * @param w 邻接矩阵
 * @return true 
 * @return false 
 */
bool Bellman_Ford::run_Bellman_Ford(Weight_Directed_Graph *G, int s, vector<vector<int>>* w){
    Initialize_Single_Source(G, s);
    for (size_t i = 0; i < G->n_V - 1; i++)
    {
        //遍历每一个边
        for (size_t u_i = 0; u_i < G->n_V; u_i++)
        {
            vertex* p = G->V[u_i];
            while (p != nullptr)
            {
                if (p->next != nullptr)
                {
                    Relax(G->V[u_i], G->V[p->next->index], w);
                }
                p = p->next;
            }
        }
    }
    //遍历每一个边
    for (size_t u_i = 0; u_i < G->n_V; u_i++)
    {
        vertex* p = G->V[u_i];
        while (p != nullptr)
        {
            if (p->next != nullptr)
            {
                if(G->V[p->next->index]->d > G->V[u_i]->d + (*w)[u_i][p->next->index]) return false;
            }
            p = p->next;
        }
    }
    return true;
}


/**
 * @brief 输出Bellman-Ford的运行结果
 * 
 * @param G 已经运行完run_Bellman_Ford后存储了运行结果的图
 * @param s 源节点下标
 */
void Bellman_Ford::output_result(Weight_Directed_Graph *G, int s){
    for (size_t i = 0; i < G->n_V; i++)
    {
        if (i != s && G->V[i]->d < 1000000000)
        {
            cout << s << ',' << i << ',' << G->V[i]->d << ';';
            cout << s << ',';
            vector<vertex*> stack;
            for (vertex* pi = G->V[i]; pi != G->V[s];)
            {
                stack.push_back(pi);
                if (pi->pi != nullptr)
                {
                    pi = pi->pi;
                }
                
            }
            while (stack.size())
            {
                cout << stack.back()->index;
                if (stack.back()->index != i)
                {
                    cout << ',';
                }
                
                stack.pop_back();
            }
            cout << endl;
        }
    }
}